Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Okay, fangen wir an. Also wir waren in dem Kapitel stehen geblieben über kürzeste Wege.

Also wir wollen kürzeste Wege in Grafen bestimmen. Und die hatte gestern mit Professor Martin schon,

und letzte Woche glaube ich, so die ersten Standard-Algorithmus mit Dijkstra kennengelernt.

Dijkstra funktioniert halt allerdings nur für nicht negative Kantengewichte,

und deswegen wollen wir uns noch ein paar andere Algorithmen für kürzeste Wege anschauen.

Und der Professor Martin hatte gestern schon mal angefangen mit dem Algorithmus von Mohr und Bellmann.

Den schreibe ich noch mal ganz kurz an.

So, das war der Algorithmus 7.18, die Grundversion von Mohr und Bellmann.

Und die ging ja recht einfach, also man initialisiert erst diese Knotenlabels auf 0 für v gleich s,

und ansonsten unendlich.

Und dann macht der Algorithmus nichts anderes als solange dieses Knotenlabel noch nicht optimal ist, verbessern wir.

Also solange es einen Bogen gibt,

sodass dieses Label von diesem Knoten echt größer ist als der Vorgängerknoten plus die Kante Cij, Kantengewicht,

dann updaten wir das Knotenlabel von dj und setzen dj gleich di plus Cij.

So, und das war es schon, also mehr macht dieser Algorithmus nicht.

Und dieser Algorithmus beruht halt auf der Beobachtung, dass halt,

also wenn halt für diese Knotenlabels gilt, dass dj immer größer gleich di plus Cij ist, dann sind wir optimal.

Und solange das halt noch nicht gilt, updaten wir und hören halt auf, wenn alle Knotenlabels optimal sind.

Gut, und dann hatte der Professor Martin auch letzte Woche gestern schon angefangen, das erste Lemma zu beweisen,

das gleich brauchen, schreibe ich das auch nochmal kurz hin.

Das macht aber nichts anderes, dass Cij d hoch k, das war nichts anderes definiert als Cij plus dki minus dkj,

immer kleiner war als Null für alle ij Element ak.

Wobei halt dieses dk von i nichts anderes war als dieses Knotenlabel in der Kartenintervention,

also nachdem diese Weilschleife k mal aufgerufen wurde.

Und das ak hattet ihr halt definiert als die Bögen in dem kürzesten Wegebaum, der halt von diesem Algorithmus bis zur Iteration k konstruiert wurde.

So, das hattet ihr alles gestern gemacht und jetzt wollen wir natürlich noch beweisen, dass diese Algorithmus auch wirklich funktioniert.

Und da machen wir jetzt weiter.

Und das nächste Lemma, was wir noch brauchen, auch ein Hilfslemma und danach können wir wirklich beweisen mit den beiden Sachen zusammen,

dass der Algorithmus auch wirklich funktioniert.

Wir zeigen, dass das, was hier rauskommt, also dass diese Konstruktion, die hier aufgebaut wird, immer ein Baum ist,

mit Wurzel s, falls der Graph keinen negativen Kreis enthält.

Also, Behauptung ist hk enthält alle Knoten von ak und alle Kanten.

Das ist eine Aborussenz.

Also, Aborussenz, also ein gerichteter Baum mit Wurzel s für alle K gleich eins bis der Algorithmus halt abrichtet.

So, was müssen wir beweisen, wenn wir zeigen wollen, dass das, was hier rauskommt,

in jeder Iteration auf jeden Fall immer ein gerichteter Baum ist.

Zum einen müssen wir, Baum ist kreisfrei, also wir müssen Kreisfreiheit zeigen.

Und es darf kreisfrei sowohl, also es darf keinen gerichteten Kreis geben, es darf aber auch keine ungerichteten Kreise geben.

Und wir müssen halt zeigen, dass es zusammenhängt ist, also im Sinne von gerichtet müssen wir halt zeigen,

dass wir von s zu jedem Knoten in diesem Baum, dass da ein Weg existiert.

Also ein gerichteter Weg von s zu allen Knoten.

Gut, dann machen wir das mal.

Also als allererstes wollen wir mal zeigen, dass das, was da rauskommt, keinen Kreis enthält.

Und wir nehmen einfach mal an, die Aussage ist falsch und es gibt einen Kreis.

Und wir gucken uns jetzt mal die Iteration an, wo der Kreis wirklich auftritt zum allerersten Mal.

Also wenn jetzt irgendwann wir einen HK finden, sodass da ein Kreis auf da ist, dann gucken wir uns mal an,

wo, an welcher Iteration davor tritt denn der Kreis zum ersten Mal auf.

Also wir nehmen mal halt an, dass K der kleinste Index ist, sodass HK einen Kreis enthält.

Und jetzt im ersten Fall nehmen wir erstmal an, dass der gerichtet ist.